1. Field of the Invention
The present invention relates to a character strings reading device for reading character strings from input image data, and more particularly to a device for reading addresses written on mails or a register, a device for reading sentences in a document, a pen input device for writing sentences into a computer with a stylus pen or the like.
2. Description of Related Art
In a conventional character strings reading device, image data are first input and then a segment corresponding to each character is cut out from the image data. Subsequently, character recognition is individually performed on each segment. In some cases, a reading result of a character string is determined until this stage. However, in order to make the reading result more accurate, restriction on an alignment (string) of words is applied to the characters of the segments. In this case, a character candidate string as an individual recognition result is collated with a word dictionary to obtain a proper character string as a word alignment.
The reading of addresses along the above processing flow will be described with reference to FIG. 1A.
In order to read an address, image data on an address area of a mail or a register are input. In this case, "words" mean address elements such as the names of To, Do, Fu and Ken (the metropolis and districts, e.g., the names of states) and the names of cities, wards, districts, towns, villages, etc.
In FIG. 1A, a segment 20 corresponding to each character is first cut out from the image data 10, and then character recognition is performed on each cut-out segment 20 to thereby obtain various character candidate strings 30. These character candidate strings 30 correspond to arrays of character candidates which are selected as characters similar to correct characters of the image data 10. At this stage, plural character candidates are selected for one segment. For example, three character candidates &lt;nishi&gt;, &lt;shina&gt;, &lt;dai&gt; are selected as a character candidate which corresponds to or similar to a segment 20 at the leftmost side. In this specification, a word consisting of a single character or an array of characters, which is represented by "romaji" (a method of writing Japanese in Roman characters) between numerals &lt;and&gt;, such as &lt;nishi&gt;, &lt;shina&gt;, &lt;dai&gt;, etc. means one character corresponding to Japanese Kanji as illustrated in the drawings.
The relation between the Kanji characters used in the drawings and the "romaji" representations thereof is shown in FIG. 1B. It should be noted, however, that each Japanese or Chinese characters has usually two or more different pronunciations according to the combination with another character or its meaning, the representations shown in FIG. 1A are not necessarily correct in the general idiomatic sense of Japanese language.
By collating the character candidate strings 30 with a dictionary for address elements, a combination of address elements (&lt;shina&gt;&lt;kawa&gt;&lt;ku&gt;)(&lt;naka&gt;&lt;nobu&gt;) is selected as a best combination, and this combination is finally selected as an address reading result 90.
This type of conventional address reading device is described in "OCR Address Reading/Letter Sorting Machine for the Ministry of Posts and Telecommunications of Japan" (by Ishikawa, et.al., NEC Technical Journal, Vol. 44, No. 3, 1991), "Japanese Address Reader-Sorter, Model TR-17" (by Torimoto, et.al., Toshiba Review, Vol. 45, No. 2, 1990), Japanese Laid-open Patent Application No. Hei-5-324899 for "Recognition Device for Addresses written on Mails", Japanese Laid-open Patent Application No. Hei-3-189780 for "Address Recognition Device".
Furthermore, conventional devices for reading sentences in a document and conventional devices for inputting sentences with a pen are described in "Implementation and Evaluation of Post-processing for Japanese Document Readers by (Takao, et. all, Transactions of Information Processing Society of Japan, Vol. 30, No. 11, 1989), "A Method of Detecting and Correcting Errors in the Japanese OCR" (by Ito, et.al., Transactions of Information Processing Society of Japan, Vol. 33, No. 5, 1992), "Natural Language Processing in Text Recognition" (by Nishino, Journal of Information Processing Society of Japan, Vol.34, No. 10, 1993), "On-line Handwritten character recognition system" of Japanese Laid-open Patent Application No. Sho-61-086883.
All characters constituting a correct character string are not necessarily contained in character candidates as an individual character recognition result. In the case of FIG. 1A, a correct character string corresponds to a combination of character candidates contained in character candidate strings 30. However, for example, if &lt;kawa&gt; does not exist at a second segment from the left side of the character candidate strings 30 and character candidate strings 30 shown in FIG. 2A are selected, the correct character string &lt;shina&gt;&lt;kawa&gt;&lt;ku&gt;&lt;naka&gt;&lt;nobu&gt; cannot be obtained by any combination of the character candidates of the character candidate strings 30.
According to a first method of finally determining the reading result in such a status, vermicular (read skip) collation (imperfect coincidence) is permitted to the character recognition. For the character candidate strings 30 of FIG. 2A, there is a possibility that &lt;shina&gt;&lt;kawa&gt;&lt;ku&gt;&lt;naka&gt;&lt;nobu&gt; or &lt;shina&gt;&lt;kawa&gt;&lt;ku&gt;&lt;nishi&gt;&lt;naka&gt;&lt;nobu&gt; is selected as a candidate 91 of the address reading result (when &lt;shina&gt;&lt;kawa&gt;&lt;ku&gt;&lt;nishi&gt;&lt;naka&gt;&lt;nobu&gt; is selected, the selection is made in consideration of an judgment that one segment covers two characters due to ambiguity of the cut-out of characters.
According to a second method, the number of character candidates is beforehand increased to reduce the possibility of omission of a correct character, and these character candidates are collated with a word dictionary. In Japanese Laid-open Patent Application No. Sho-62-251986 for "Erroneously-read Character Correcting Processing Device", it is described that another character which is similar to each character candidate is added after the character recognition and then these characters are also collated with a word dictionary. If this method is applied to the case of FIG. 2A, &lt;kawa&gt; is added to the character candidates as a similar character to &lt;ko&gt;.
According to a third method, a character coincidence condition for the collation is expanded when the collation with the word dictionary fails. For example, in Japanese Laid-open Patent Application No. Hei-3-73086 for "Character Recognition Post-processing system", it is described that character coincidence is judged as the number of strokes in a Chinese character is nearer. In the case of FIG. 2A, since the number of the strokes of &lt;ko&gt; or a group of {&lt;ko&gt;, &lt;hachi&gt;, &lt;yama&gt;} is near to that of &lt;kawa&gt;, it is regarded as being coincident with &lt;kawa&gt;.
According to a fourth method, a character candidate is replaced by another character when the collation of the character candidate with the word dictionary fails, and then the new character candidate is collated with the word dictionary again. In Japanese Laid-open Patent Application No. Sho-58-4490 for "Character Recognition Device", a first candidate character string is first collated with the word dictionary. When the collation fails, it is replaced by a second candidate or subsequent candidates, and then a character string having a new candidate is collated with the word dictionary. Furthermore, in Japanese Laid-open Patent Application No. Hei-5-46814 for "Character Reading Device", a character candidate is replaced by another character having an outline which is similar to the outline of the character candidate, and then it is collated with the word dictionary again.
According to a fifth method, a collating condition or the like is altered and the processing from the character recognition step is re-tried. In Japanese Laid-open Patent Application No. Hei-2-300972 for "Electronic dictionary", a slice level at which multi-value image data are digitalized is altered and then the character recognition is tried again.
Considering that the character recognition is also applied to various character strings containing handwritten character strings, there is a low possibility that all characters constituting a correct character string are obtained as character candidates of the cut-out recognition result by the present character cut-out and character recognition performance. Accordingly, it is extremely rare that the correct character string is read out by a character strings reading device which is based on the assumption that all the characters constituting the correct character string are contained in the character candidates.
Therefore, there must be indispensably provided a method of enabling an accurate reading even when correct characters are omitted from a correct character string. The above five methods have been proposed to satisfy this requirement, however, the methods (first to fifth methods) as described above have the following disadvantages.
The first method is a basic method, but, involves a disadvantage that a large number of character candidates are necessarily selected as reading results (i.e., a large number of possibilities (candidates) exist), and thus information quantity is too insufficient to determine an accurate reading result by screening a large number of candidates (narrowing the possibility).
In the second method, the number of possibilities or candidates is beforehand increased, so that there occur many cases where a large number of possibilities (candidates) are selected as final reading results. Furthermore, as the number of character candidates is increased, a data amount to be processed and a processing time are generally increased in accordance with combinations thereof.
In the third method, a large number of candidates are screened, however, there are provided a large number of reading results which are close to each other in the number of strokes of chinese character, so that an actual effect is insufficient. In the fourth and fifth methods, the processing efficiency is low because the collation with the word dictionary is repeated every time a character candidate is varied.
Furthermore, even when a correct character is contained in a character candidate string, there are some cases where a reading result based on another character candidate exists, i.e., the character recognition has no vermiculation, and it competes against the correct character. FIG. 2B shows this case. In FIG. 2B, both &lt;nishi&gt; and &lt;minami&gt; exist as a character candidate at a fourth segment from the left side, and thus each of (&lt;shina&gt;&lt;kawa&gt;&lt;ku&gt;&lt;nishi&gt;&lt;shina&gt;&lt;kawa&gt;) and (&lt;shina&gt;&lt;kawa&gt;&lt;ku&gt; &lt;minami&gt;&lt;shina&gt;&lt;kawa&gt;) are selected as a combination of character candidates which is subjected to no read-skip (no vermiculation). The conventional first to fifth methods as described above are proposed on the assumption that the character reading is not well performed or a read skip occurs, and thus these methods are not applicable to precisely select a character candidate in a case where plural character candidates (reading results) are obtained with no read skip. In such a case that plural candidates complete against one another, these conventional methods utilize reliability of a character candidate as an assist factor at the best.
For example, in the case of FIG. 2B, if &lt;nishi&gt; has higher reliability as a character candidate (i.e., higher candidate order) than &lt;minami&gt;, &lt;shina&gt;&lt;kawa&gt;&lt;ku&gt;&lt;nishi&gt;&lt;shina&gt;&lt;kawa&gt; is preferentially determined as a final reading result. However, if a character candidate is coercively determined in such a condition that sufficient information is not obtained when plural character candidates complete against one another, a reading error would occur.